1. Field of the Invention
This invention relates to database systems and, more particularly, to entry storage in database systems. The invention also relates to query matching methodologies employed in database systems.
2. Description of the Related Art
Database systems are serving increasingly important roles in today""s society. The amount of data that may be stored by typical database systems is growing at staggering rates, and providing expedient and flexible access to the data iand often vital. However, the job of designing database systems which perform in an optimal manner is difficult.
A particularly important consideration in database design is to store the data so that it can be used for a wide variety of applications and such that the manner in which it may be used can be changed quickly and easily. It is further often desirable to allow additional data types or categories to be added without significantly affecting other portions of the database system.
Unfortunately, it is remarkably difficult to change the way data is used and organized in many database systems, and to allow for additional data types and categories. Modifications can set off a chain reaction of changes to programs and other components of the database system, and hence can be exceedingly expensive to accomplish. Consequently, data processing has tended to become frozen into its old data structures. Additionally, designers of database systems tend to make numerous intricate trade-offs between one aspect of the design and another, thus leading to a less than optimal resulting design.
To elaborate further, storing information in a database system is usually done by exact type; that is, a record stored in a database system typically has a certain number and type of fields, such as a tuple in a relation of a relational database. Each field may be defined to store a particular type of data, such as string data, integer data, boolean data, or some other data type, as desired. If a user wants to look-up information in the database, the user must look-up the exact record type (i.e., records of different types are typically searched independently). Thus, if data in which the searcher is interested may be in a record of any one of several different types, the searcher must know in advance which record types might exist, or have some explicit way of asking for all types. The searcher is then required to explicitly look through all possible record types to find the particular record of interest. This complicates the software associated with the search engine and can practically limit the number of different record types that can be maintained.
Furthermore, fields in a record in a database typically do not refer to other records. This reduces the amount and kind of information a single record typically holds. Consequently, databases are limited by their inability to store and manipulate records that are sets of records.
In addition, a record in a typical database is usually not associated with characteristics apart from the actual data itself For example, when data is found, there is no way to associate behavior with the record that changes with the record type, thus allowing the program to use various records returned by the match in a single way to achieve record-type specific results.
Regarding another aspect of database systems, the usual way of specifying attributes or properties in a database is by a simple set of  less than name, value greater than  pairs, where the values are either restricted to strings or else are of arbitrary type (type xe2x80x9canyxe2x80x9d). There is no way to restrict type in these  less than name, value greater than  pairs, and hence, there is no enforcement that a particular name must always have a value of a particular type. For example, in a hypothetical printer, the xe2x80x9cspeedxe2x80x9d attribute, representing how many pages-per-minute the printer can print, should be enforced as an integer to ensure a user does not set it to something else, such as xe2x80x9cabout 10 ppmxe2x80x9d or xe2x80x9c8 to 10.xe2x80x9d The same kind of problem exists if the values can be objects of any type. In that case, a user can set the attribute to an integer object instead of a string object but still cannot prevent another user from incorrectly storing a string object in an attribute that should only be set to integers.
Furthermore, previous systems have no enforcement of relationships between different attributes (e.g., that one attribute should exist if and only if another attribute also exists). For example, given three exemplary attributes for a printer: resolution (dots per inch), speed (pages per minute), and color (vs. black and white), in reality, many printers can perform different combinations of these attributes. For example, a typical color printer might be described as:
5 pages per minute at 600 dots per inch in black and white;
7 pages per minute at 300 dots per inch in black and white;
1 page per minute at 300 dots per inch in color.
Whereas a given attribute can have multiple values, some conventional systems allow attributes to have multiple values, and these systems might represent the given attributes in the following manner:
speed={1,5,7}
resolution={300, 600}
color={true,false}but this does not express the interrelationships between the pairs of attributes. Expressly, there is no representation and enforcement of the three interrelationships:
{speed: 1, resolution: 300, color: true};
{speed: 7, resolution: 300, color: false};
{speed: 5, resolution: 600, color: false}.
Accordingly, it is desirable to provide a database system allowing for polymorphic entry, entry matching and manipulation including sets of entries, to thereby allow more efficient searching and to allow simplified software implementation where many different types exist. It would further be desirable to provide a system where entries may define their own behavior according to type. Additionally, it would be desirable to have type-safe attribute matching in a database system and have enforcement of relationship between attributes.
The problems outlined above are solved by a method and system for storing and searching entries in a database consistent with the present invention. In one embodiment, a computer system implements a database system wherein one or more entry databases store a plurality of entries. Each entry is of a given type that defines the fields of the entry. Each of the fields contains or identifies an object with associated attributes or data. The type of each entry may further define behavior in the form of methods the entry is configured to implement. An entry type which is a subtype of another inherits all of the fields and behavior of its supertype, and contains additional fields and/or defines new or modified behavior. Entries may be expressed in a Java(trademark) class of the Java(trademark) programming language. Similarly, in one implementation, each field is expressed in a defined class.
The database system may further employ a search engine which allows queries to be made upon entries in the database. In one implementation, the queries include a read operation, a take operation, and a notify operation. Each query request includes a command indicating the type of operation and a template which is an entry object having some or all of its fields set to specified values that must be matched exactly. Other fields of the template entry may be specified as wildcards, whose values do not matter. The polymorphic entry and entry matching technique advantageously allows a query to be made which might result in a match of an entry which is the same type as the template entry or which is a subtype of the template entry. This allows for efficient searching and for simplified implementation of the search engine. Furthermore, the search engine need not be aware of all possible subtypes which might exist. Finally, since each entry has an associated class, an entry may define its own behavior by supporting one or more methods. A method of a particular entry may be invoked by a program to implement various functionality, such as equivalence checking.
The search engine may further be configured to create an index for entries having characteristics which are commonly specified by queries. That is, the search engine may detect a pattern of usage and create an index which points to entries having attributes which are commonly specified by received templates. In this manner, expedient entry searching can be accomplished.
Additionally, the search engine may further be configured to store sets of entries in a single record. These sets of entries are matched using sets of templates. In one implementation, operations similar to single entry implementation operations, such as read, take, write, and notify, may be performed on sets of entries.